package com.LeeCode;

import java.util.Arrays;

/**
 * 咒语和药水的成功对数
 */

public class Code2300 {
    public static void main(String[] args) {
        int[] spells = {5, 1, 3};
        int[] potions = {1, 2, 3, 4, 5};
        long success = 7;
        System.out.println(Arrays.toString(new Code2300().successfulPairs(spells, potions, success)));
    }

    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int[] ans = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            ans[i] = lowerBound(potions, spells[i], success);
        }

        return ans;
    }

    private int lowerBound(int[] potions, int spell, long success) {
        int left = -1, right = potions.length, mid;

        while (left + 1 < right) {
            mid = left + (right - left) / 2;
            if ((long) potions[mid] * spell >= success) {
                right = mid;
            } else {
                left = mid;
            }
        }

        return potions.length - right;
    }
}
